package com.wfm.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

public class PThree2最长有效括号{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestValidParentheses(String s) {
        if(s.length()<2) return 0;
        int[] dp = new int[s.length()];
        int max =0;
        for (int i = 1; i < s.length(); i++) {
            if(s.charAt(i)==')'){
                int preLen = dp[i-1];
                int pre = i-preLen-1;
                if(pre>=0&&s.charAt(pre)=='('){
                    dp[i]=dp[i-1]+2;
                    if(pre-1>=0){
                        dp[i]+=dp[pre-1];
                    }
                }
                max = Math.max(dp[i],max);
            }
        }
        return max;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PThree2最长有效括号().new Solution();
    }
}